package leetCode;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;


public class LeetCode_day6 {

	
	public static void removeNthNodeFromEndOfList(ListNode node, int ind, int del){
		if(ind < del-1) 
			if(node == null) return;
			else removeNthNodeFromEndOfList(node.next, ++ind, del);
		if(ind == del-1)
			if(node.next != null){
				node.next = node.next.next;
				return;
			}else return;
	}
	
	/**
	 * Suppose a sorted array is rotated at some pivot unknown to you beforehand.
	 * (i.e., 0 1 2 4 5 6 7 might become 4 5 6 7 0 1 2).
	 * You are given a target value to search. 
	 * If found in the array return its index, otherwise return -1.
	 * You may assume no duplicate exists in the array.
	 * @param a
	 * @param val
	 * @return
	 */
	public static int searchInRotatedSortedArray(int[] a, int val){
		if(a == null) return -1;
		
		if(val == a[0]) return 0;
		else if(val > a[0]){
			int ind = 0;
			while(val > a[++ind]);
			if(ind >= a.length) return -1;
			else return ind;
		}else{
			int ind = a.length;
			while(a[--ind] > val){
				System.out.println(ind);
			}
			if(a[ind] != val) return -1;
			else return ind;
		}
	}
	
	/**
	 * Given a sorted array of integers, 
	 * find the starting and ending position of a given target value.
	 * Your algorithm's runtime complexity must be in the order of O(log n).
	 * If the target is not found in the array, return [-1, -1].
	 * For example,
	 * Given [5, 7, 7, 8, 8, 10] and target value 8,
	 * return [3, 4].
	 * 
	 * Just like binary search.
	 * @param a
	 * @param val
	 * @return
	 */
	public static int[] searchForARange(int[] a, int start, int end, int val){
		if(a == null) return new int[]{-1,-1};
		if(start == end){
			if(a[start] != val) return new int[]{-1,-1};
			else return new int[]{start, end};
		}
		if(start < end){
			int mid = start + (end-start) / 2;//avoid overflow
			int[] res1 = searchForARange(a, start, mid, val);
			int[] res2 = searchForARange(a, mid+1, end, val);
			
			int[] fail = new int[]{-1,-1}; int[] res = fail;
			if(!Arrays.equals(fail, res1)) res = res1;
			if(!Arrays.equals(fail, res2)){
				if(Arrays.equals(fail, res))
					res = res2;
				else{
					if(res2[0] < res[0]) res[0] = res2[0];
					if(res2[1] > res[1]) res[1] = res2[1];
				}
			}
			return res;
		}else{
			return new int[]{-1,-1};
		}
	}
	
	/**
	 * Given a sorted array and a target value, 
	 * return the index if the target is found. 
	 * If not, return the index where it would be if it were inserted in order.
	 * You may assume no duplicates in the array.
	 * Here are few examples.
	 * [1,3,5,6], 5 → 2
	 * [1,3,5,6], 2 → 1
	 * [1,3,5,6], 7 → 4
	 * [1,3,5,6], 0 → 0
	 * @param a
	 * @param val
	 * @return
	 */
	public static int searchInsertPosition(int[] a, int start, int end, int val){
		if(a == null) return -1;
		if(start == end){
			if(a[start] == val) return start;
			else if(a[start] < val){
				return start+1;
			}else return start-1;
		}
		
		int mid = start + (end - start)/2;
		if(a[mid] == val) return mid;
		else{
			if(a[mid] < val) return searchInsertPosition(a, mid, end, val);//if here is mid + 1, incorrect
			else return searchInsertPosition(a, start, mid-1, val);
		}
	}
	
	/**
	 * 
	 * @param board
	 * @return
	 */
	public static boolean validSudoku(int[][] board){
		if(board == null || board.length != 9 || board[0].length != 9) return false;

		boolean[] marker = new boolean[10];
		//check all rows
		for(int i = 0 ; i < 9 ; i++){
			Arrays.fill(marker, false);
			for(int j = 0 ; j < 9 ; j++){
				if(board[i][j] != 0){
					if(marker[board[i][j]]) return false;
					else marker[board[i][j]] = true;
				}
			}
		}
		//check all columns
		for(int i = 0 ; i < 9 ; i++){
			Arrays.fill(marker, false);
			for(int j = 0 ; j < 9 ; j++){
				if(board[j][i] != 0){
					if(marker[board[j][i]]) return false;
					else marker[board[j][i]] = true;
				}
			}
		}
		//check all sub-boards
		for(int i = 0 ; i < 3 ; i++){
			for(int j = 0 ; j < 3 ; j++){
				int start1 = i*3, start2 = j*3;
				Arrays.fill(marker, false);
				for(int p = 0 ; p < 3 ; p++){
					for(int q = 0 ; q < 3 ; q++){
						int x = start1+p, y = start2 + q;
						if(board[x][y] != 0){
							if(marker[board[x][y]]) return false;
							else marker[board[x][y]] = true;
						}
					}
				}
			}
		}
		return true;
	}
	
	/**
	 * Very classical problem for backtracking algorithm.
	 * DFS in the solution tree.
	 * 
	 * @param board
	 */
	
	public static boolean isValid(char[][] board, int row, int col, int val){
		//boolean[][] mark = new boolean[3][10];
		//for(int i = 0 ; i < 3 ; i++) Arrays.fill(mark[i], false);
		//board[row][col] = (char)('1'+val-1);
		
		for(int i = 0 ; i < 9 ; i++){
			//check row
			if(i != col && board[row][i] != '.'){
				int value = Character.getNumericValue(board[row][i]);
				if(value == val) {
					board[row][col] = '.';
					return false;
				}
			}
			//check col
			if(i != row && board[i][col] != '.'){
				int value = Character.getNumericValue(board[i][col]);
				if(value == val) {
					board[row][col] = '.';
					return false;
				}
			}
			//check subboard
			//decide which subboard
			int row_t = 3 * (row / 3) + i / 3;
			int col_t = 3 * (col / 3) + i % 3;
			if(row_t == row && col_t == col) continue;
			if(board[row_t][col_t] != '.'){
				int value = Character.getNumericValue(board[row_t][col_t]);
				if(value == val) {
					board[row][col] = '.';
					return false;
				}
			}
		}
		return true;
	}
	
	public static boolean DFS(List<int[]> pos , char[][] board, int step){
		if(step == pos.size()) return true;
		int[] position = pos.get(step);
		for(int k = 1 ; k < 10 ; k++){
			if(isValid(board, position[0], position[1], k))
				if(DFS(pos, board, step+1)) return true;
		}
		return false;
	}
	
	public static boolean sudokuSolver(char[][] board){
		List<int[]> list = new ArrayList<int[]>();
		for(int i = 0 ; i < 9 ; i++)
			for(int j = 0 ; j < 9 ; j++)
				if(board[i][j] == '.')
					list.add(new int[]{i,j});
				
		return DFS(list, board, 0);
	}
	
	/**
	 * ! The count-and-say sequence is the sequence of integers beginning as follows:
	 * 1, 11, 21, 1211, 111221, ...
	 * 1 is read off as "one 1" or 11.
	 * 11 is read off as "two 1s" or 21.
	 * 21 is read off as "one 2, then one 1" or 1211.
	 * Given an integer n, generate the nth sequence.
	 * Note: The sequence of integers will be represented as a string.
	 * 
	 * Change in place.
	 * @param n
	 * @param s
	 */
	public static void countAndSay(int n, StringBuilder s){
		if(n == 0) {
			System.out.println(s);
			return;
		}
		int count = 1, ind = 1;
		char c = s.charAt(0);
		while(ind < s.length()){
			if(s.charAt(ind) == c){
				count++;
				ind++;
			}else{
				char[] temp = new char[2];
				temp[0] = (char)(count+'0');
				temp[1] = c;
				s.insert(ind-count, temp);
				ind = ind - count + 2;
				s.delete(ind, ind+count);
				if(ind >= s.length()) break;
				count = 0;
				c = s.charAt(ind);
			}
		}
		char[] temp = new char[2];
		temp[0] = (char)(count+'0');
		temp[1] = c;
		s.insert(ind-count, temp);
		ind = ind - count + 2;
		s.delete(ind, ind+2);
		
		countAndSay(n-1, s);
	}
	
	/**
	 * @param args
	 */
	public static void main(String[] args) {
		// TODO Auto-generated method stub
		System.out.println(searchInRotatedSortedArray(new int[]{4,5,6,7,0,1,2,3}, 5));
		int[] res = searchForARange(new int[]{1,2,2,3,4,5,5,6,7,8,8,9}, 0, 11, 2);
		System.out.println(searchInsertPosition(new int[]{0,1,2,5,6,7}, 0, 5, 3));
		//int[][] board = new board{};
		System.out.println((char)(5+'0'));
		char[][] board = new char[9][9];
		countAndSay(4, new StringBuilder("11"));
		System.out.println();
	}

}

/**
 * while(val > a[++ind]); correct, a[ind] = val
 * while(val > a[ind++]); not correct
 */
